//颜色分类
class Solution {
public:
    void sortColors(vector<int>& nums) {
        //一共有3个指针：left，right，i
        //i：遍历数组
        //left ：指向红色区域的最右侧
        //right ：指向蓝色区域的最左侧
        //遍历过程中一共会把数组划分为4个区域
        //[0,left]：已处理为红色区域
        //[left+1,i]：已处理为白色区域
        //[i+1,right-1]：待处理区域
        //[right,n-1]：已处理为蓝色区域
        for(size_t i = 0,left = -1,right = nums.size() ; i < right ; ++i)
        {
            if(nums[i] == 0) swap(nums[++left],nums[i]);
            else if(nums[i] == 2) swap(nums[--right],nums[i--]);
        }
    }
};

//排序数组
class Solution {
public:
    int GetRandomNum(vector<int>& nums , int left , int right)
    {
        int r = rand();
        return nums[(r % (right - left + 1)) + left];
    }
    void QuickSort(vector<int>& nums , int begin , int end)
    {
        if(begin >= end) return;
        int key = GetRandomNum(nums,begin,end);
        int left = begin-1 , right = end + 1 , i = begin;
        while(i < right)
        {
            if(nums[i] < key) swap(nums[++left],nums[i++]);
            else if(nums[i] > key) swap(nums[--right] , nums[i]);
            else ++i;
        }
        //[begin , left] [left+1,right-1] [right,end]
        QuickSort(nums,begin,left);
        QuickSort(nums,right,end);
    }
    vector<int> sortArray(vector<int>& nums) {
        srand(time(nullptr));
        int n = nums.size();
        QuickSort(nums,0,n-1);
        return nums;
    }
};

//数组中的第k个最大元素
class Solution {
public:
    int QuickSelect(vector<int>& nums, int begin, int end, int k) {
        if (begin == end)
            return nums[begin];
        int left = begin - 1, right = end + 1, i = begin,
            key = GetRandomNum(nums, begin, end);
        while (i < right) {
            if (nums[i] < key)
                swap(nums[++left], nums[i++]);
            else if (nums[i] > key)
                swap(nums[--right], nums[i]);
            else
                i++;
        }
        //[begin , left] [left+1 , right-1] [right , end]
        int num1 = end - right + 1; // num1表示[right,end]中元素的个数
        int num2 = right - 1 - left; // num2表示[left+1 , right-1]中元素的个数
        int num3 = left - begin + 1; // num3表示[begin , left]中元素的个数

        if (k <= num1)
            return QuickSelect(nums, right, end, k);
        else if (k <= (num1 + num2))
            return key;
        else
            return QuickSelect(nums, begin, left, k - num1 - num2);
    }

    int GetRandomNum(vector<int>& nums, int left, int right) {
        int r = rand();
        return nums[(r % (right - left + 1)) + left];
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        srand(time(nullptr));
        return QuickSelect(nums, 0, n - 1, k);
    }
};

//最小k个数
class Solution {
public:
    int GetRandom(vector<int>& arr , int left , int right)
    {
        int r = rand();
        return arr[(r % (right - left + 1)) + left];
    }
    void QuickSelect(vector<int>& arr, int begin, int end, int k) 
    {
        if(begin == end) return;
        int key = GetRandom(arr, begin , end);
        int left = begin-1 , right = end+1 , i = begin;
        while(i < right)
        {
            if(arr[i] < key) swap(arr[++left],arr[i++]);
            else if(arr[i] > key) swap(arr[--right],arr[i]);
            else i++;
        }
        // [begin,left] [left+1 , right-1] [right , end]
        int a = left - begin + 1;
        int b = right-left-1;
        //分情况讨论
        if(a > k) QuickSelect(arr,begin,left,k);
        else if(a + b >= k) return;
        else QuickSelect(arr,right,end,k-a-b);
    }
    vector<int> smallestK(vector<int>& arr, int k) 
    {
        if(k == 0) return{};
        srand(time(nullptr));
        QuickSelect(arr,0,arr.size()-1,k);
        return {arr.begin(),arr.begin()+k};
    }
};









